package leetcode_81_100;

import utils.TreeNode;

public class isValidBST_98 {
    /**
     * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        if ( (root.left !=null ? root.left.val <root.val : true) && (root.right !=null ? root.right.val > root.val : true) ) {
            return function(root,root.left,root.val,0) && function(root,root.right,root.val,1);
        }else
            return false;
    }

    /**
     * 递归判断
     * 我的思路失败，因为递归到深层的枝叶，还需要和上面很多层前许多不确定的节点比较值
     * 因为二叉搜索树右子树上所有节点都要大于根节点。
     * @param root 根节点
     * @param cur  当前节点
     * @param pre  当前节点的上一个节点的值
     * @param flag 当前节点是上一个节点的哪个节点，0左，1右
     * @return
     */
    boolean function(TreeNode root,TreeNode cur,int pre,int flag){
        if (cur==null)
            return true;

        if ( (cur.left !=null ? cur.left.val < cur.val : true) && (cur.right !=null ? cur.right.val > cur.val : true) ) {
            //左节点小于当前节点，右节点大于当前节点
            //如果哪个为null, 直接返回true
            if (flag == 0 &&  cur.right !=null  ) { //当前节点是上一个节点的左节点
                if (cur.right.val >= pre)          //右节点大于等于上一个节点
                    return false;
            } else if(flag==1 && cur.left !=null){
                if (cur.left.val  <= pre)          //左节点小于等于上一个节点
                    return false;
            }
        }else
            return false;

        return function(root, cur.left, cur.val, 0) && function(root, cur.right, cur.val, 1);
    }

    /**
     * 高解
     *利用中序遍历递归，左中右
     * 从左边最深层到达右边最深层，完美符合二叉搜索树的条件
     */
    long pre = Long.MIN_VALUE;
    public boolean isValidBST2(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 访问左子树
        if (!isValidBST2(root.left)) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // 访问右子树
        return isValidBST2(root.right);
    }

}
